large_numbersfandomcom-20200214-history
Archimedes' cattle problem
Archimedes' cattle problem is a problem in Diophantine analysis whose solutions involve fairly large numbers.http://www.mcs.drexel.edu/~crorres/Archimedes/Cattle/Statement.html The "Cattle of the Sun" consist of four herds: white (W), black (B), dappled (D), and yellow (Y), and each cattle is a bull or a cow. Capital letters denote the number of bulls in each herd, and lowercase letters the number of cows. The system is subject to the following constraints: :\(W = (1/2 + 1/3)B + Y\) :\(B = (1/2 + 1/3)D + Y\) :\(D = (1/6 + 1/7)W + Y\) :\(w = (1/3 + 1/4)(B + b)\) :\(b = (1/3 + 1/4)(D + d)\) :\(d = (1/3 + 1/4)(Y + y)\) :\(y = (1/3 + 1/4)(W + w)\) The first problem asks for the minimum positive size of the entire herd. The second problem asks the same question, but with the additional constraints that \(W + B\) is a perfect square and \(D + Y\) is a triangular number. The first problem can be solved by expressing the system of equations in matrix form \(\mathbf{Mx} = \mathbf{0}\), where M is a 7×8 matrix and x is the solution vector. The system has infinitely many linearly dependent solutions. By expressing these solutions in the form \(\mathbf{y}k\) where \(\mathbf{y}\) is a vector of coprime positive integers, we have \(\sum \mathbf{y}\) as the solution, which turns out to be 50,389,082 cattle. The second problem is more difficult, and the solution of approximately \(7.76 \times 10^{206544}\) cattle was not found until 1965. Progress in solving the problem was hindered by the lack of sufficiently powerful computers until the 20th century. Nowadays, the problem can be solved on a personal computer in a few seconds. Computing the solution(s) In 2001, Antti Nygrén of the University of Oulu (Linnanmaa, Oulu, Finland), developed an algorithm that involved only integer arithmetic that applies linear transformation and infinite descent in solving quadratic Diophantine equations and that can be easily used to produce several numerical solutions to the Archimedes' cattle problem.http://www.mcs.drexel.edu/~crorres/Archimedes/Cattle/isbn9514259327.pdf Below is a program adapted from the Mathematica programhttp://www.mcs.drexel.edu/~crorres/Archimedes/Cattle/computer2/NygrenMathematica.html that implements Nygrén's algorithm and also determines the numbers of the eight different types of cattle: L11 = 109931986732829734979866232821433543901088049 L12 = 392567302329690546856394748066206816187916440 L21 = 30784636507697855142356992218944109072681060 L22 = L11 L = [L11,L12,L21,L22] r1 = 300426607914281713365 r2 = 84129507677858393258 L2 = [for a,b in zip(L_row,L_col)) for L_col in zip(*L) for L_row in L] L4 = [for a,b in zip(L2_row,L2_col)) for L2_col in zip(*L2) for L2_row in L2] L8 = [for a,b in zip(L4_row,L4_col)) for L4_col in zip(*L4) for L4_row in L4] L16 = [for a,b in zip(L8_row,L8_col)) for L8_col in zip(*L8) for L8_row in L8] L32 = [for a,b in zip(L16_row,L16_col)) for L16_col in zip(*L16) for L16_row in L16] L64 = [for a,b in zip(L32_row,L32_col)) for L32_col in zip(*L32) for L32_row in L32] L128 = [for a,b in zip(L64_row,L64_col)) for L64_col in zip(*L64) for L64_row in L64] L256 = [for a,b in zip(L128_row,L128_col)) for L128_col in zip(*L128) for L128_row in L128] L512 = [for a,b in zip(L256_row,L256_col)) for L256_col in zip(*L256) for L256_row in L256] L1024 = [for a,b in zip(L512_row,L512_col)) for L512_col in zip(*L512) for L512_row in L512] L1152 = [for a,b in zip(L1024_row,L128_col)) for L128_col in zip(*L128) for L1024_row in L1024] L1160 = [for a,b in zip(L1152_row,L8_col)) for L8_col in zip(*L8) for L1152_row in L1152] L1164 = [for a,b in zip(L1160_row,L4_col)) for L4_col in zip(*L4) for L1160_row in L1160] v0k0 = ((L116400) * r1) + ((L116401) * r2) #1 u0k0 = ((L116410) * r1) + ((L116411) * r2) #1 q1 = 957 * ((u0k0 * v0k0) ** 2) q2 = q1/4657 whitebulls = 2226 * q1 blackbulls = 1602 * q1 yellowbulls = 891 * q1 dappledbulls = 1580 * q1 whitecows = 7206360 * q2 blackcows = 4893246 * q2 yellowcows = 5439213 * q2 dappledcows = 3515820 * q2 totalbulls = whitebulls + blackbulls + yellowbulls + dappledbulls totalcows = whitecows + blackcows + yellowcows + dappledcows totalcattle = totalbulls + totalcows if __name__ '__main__': f = open('solved_totalcattle.txt', 'w') f.write('%s\n' % totalcattle) f.close() Sources